#！usr/bin/env/python3
#-*- coding:utf8 -*-
def insertionSort(S):
    '''插入排序，输入为需要的排序列表，输出为排序完成的列表'''
    length=len(S)#需要排序列表的长度
    temp=[S[0]]
    for i in range(1,length):#输入数组依次插入
        for j in range(len(temp)-1,-1,-1):#与完成有序排列的对比
            if S[i]>=temp[j]:#如果大于完成排序列表的则插入后面
                temp.insert(j+1,S[i])
                break
            elif S[i]<temp[j] and j==0:#如果小于完成排序列表且完成排序列表搜索完成
                temp.insert(j,S[i])
                break
            pass
        pass
    pass
    return temp
    pass

if __name__=='__main__':
    S=[90,310,50,4,6,9,7,50]
    newS=insertionSort(S)
    print(newS)
